显然,在一个强联通分量中,只要有一个城市与联通,那么整个分量就与联通。
于是我们可以缩点,统计它的入度。如果入度为,我们就从向这个缩点连一条边,如果入度不为0,说明其他城市可以到达它,我们就不需要单独连边。
最后,注意特判与在同一强联通分量的点。
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
const int MAXN = 5000;
int n , m , s , u , v;
vector< int > Graph[ MAXN + 5 ];
int dfn[ MAXN + 5 ] , low[ MAXN + 5 ] , depth , cnt;
int bel[ MAXN + 5 ] , In[ MAXN + 5 ];
bool is[ MAXN + 5 ];
stack< int > S;
void Tarjan( int u ) {
dfn[ u ] = low[ u ] = ++ depth;
S.push( u ) , is[ u ] = 1;
int v;
for( int i = 0 ; i < Graph[ u ].size() ; i ++ ) {
v = Graph[ u ][ i ];
if( !dfn[ v ] ) {
Tarjan( v );
low[ u ] = min( low[ u ] , low[ v ] );
}
else if( is[ v ] )
low[ u ] = min( low[ u ] , dfn[ v ] );
}
if( dfn[ u ] == low[ u ] ) {
++ cnt;
do{
v = S.top( );
S.pop( ); is[ v ] = 0;
bel[ v ] = cnt;
}while( u != v );
}
}
int main( ) {
scanf("%d %d %d",&n,&m,&s);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v);
Graph[ u ].push_back( v );
}
for( int i = 1 ; i <= n ; i ++ )
if( !dfn[ i ] ) Tarjan( i );
for( int i = 1 ; i <= n ; i ++ )
for( int j = 0 ; j < Graph[ i ].size( ) ; j ++ ) {
int u = bel[ i ] , v = bel[ Graph[ i ][ j ] ];
if( u != v ) In[ v ] ++;
}
int Ans = 0;
for( int i = 1 ; i <= cnt ; i ++ )
if( !In[ i ] && i != bel[ s ] ) Ans ++;
printf("%d\n",Ans);
return 0;
}